/**
 * @projectName algorithm
 * @package PACKAGE_NAME
 * @className PACKAGE_NAME.FastSort
 */

import util.GeneratorRandomArr;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * FastSort
 * @description 快速排序
 * 原理：随机选择一个数作为中间数，左边是小于该数的，中间范围是等于本身的，右边是大于该数的
 * 使用空间复杂度O(N)
 * 时间复杂度：O(N*logN)
 * @author answer_wx
 * @date 2022/6/28 18:03
 * @version 1.0
 */
public class FastSort02 {
    // 排序范围，数组角标s-e的范围，默认e>=s
    public static int[] process(int[] arr) {
        int length = arr.length;
        if (length < 2) {
            return arr;
        }
        LinkedList pivots = new LinkedList();
        ArrayList lefts = new ArrayList();
        ArrayList rights = new ArrayList();
        int index = (int) (Math.random() * length);
        int pivot = arr[index];
        for (int i = 0; i < length; i++) {
            if (arr[i] == pivot) {
                pivots.add(pivot);
            } else if (arr[i] < pivot) {
                lefts.add(arr[i]);
            } else {
                rights.add(arr[i]);
            }
        }
        int[] rlefts = process(toArr(lefts));
        int[] rrights = process(toArr(rights));
        int[] rpivots = toArr(pivots);
        int[] result = new int[length];
        for (int i = 0; i < rlefts.length; i++) {
            result[i] = rlefts[i];
        }
        for (int i = 0; i < rpivots.length; i++) {
            result[rlefts.length + i] = rpivots[i];
        }
        for (int i = 0; i < rrights.length; i++) {
            result[rlefts.length + rpivots.length + i] = rrights[i];
        }
        return result;
    }

    public static int[] toArr(List list) {
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = (int) list.get(i);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] generator = GeneratorRandomArr.generator(100, 100);
        for (int i = 0; i < generator.length; i++) {
            System.out.print(generator[i] + ",");
        }
        System.out.println();
        int[] process = process(generator);
        for (int i = 0; i < process.length; i++) {
            System.out.print(process[i] + ",");
        }
    }
}